using System;
using System.Collections.Generic;
using System.Collections;

namespace Graph
{
	public class AlgorithmPartition
	{
		private UndirectGraph graph;
		private int countOfSubsets;
		
		public AlgorithmPartition (UndirectGraph graph, int countOfSubsets)
		{
			this.graph = graph;
			this.countOfSubsets = countOfSubsets;
		}
		
		public int[] solveProblem ()
		{
			int[] res = null;
			
			return res;
		}
		
		public Partition getStartHeuristic1 ()
		{
			int[] labels = new int[this.graph.N];
			
			// Labeling
			for (int i = 0; i < this.graph.N; i++)
			{
				labels[i] = i % this.countOfSubsets;
			}
			
			int[] InterEdges = new int[this.countOfSubsets];
			int sumOfAllInterSubsetEdges = 0;
			// Für jeden Knoten
			for (int i = 0; i < this.graph.N; i++)
			{
				// Für jede Kantenmenge der Adjazenzliste
				foreach(List<Kante> es in this.graph.E[i].Values)
				{
					// Für jede Kante der Kantenmenge (besteht evtl. aus parellen)
					foreach(Kante e in es)
					{
						if (labels[i] != labels[e.Nach])
	                    {
	                        InterEdges[i % this.countOfSubsets]++;
	                        sumOfAllInterSubsetEdges++;
                      	}
					}
				}
			}
			
			sumOfAllInterSubsetEdges /= 2;
			
			Partition res = new Partition (labels, InterEdges, this.countOfSubsets, sumOfAllInterSubsetEdges);
			
			return res;
		}
		
		public Partition getStartHeuristic2 ()
		{
			int[] labels = new int[this.graph.N];
			
			int minsize = this.graph.N / this.countOfSubsets;
			
			// Labeling
			for (int i = 0; i < this.countOfSubsets; i++)
			{
				for (int j = 0; j < minsize; j++)
				{
					labels[minsize * i + j] = i;
				}
			}
			
			// Nachlabeln
			for (int i = this.countOfSubsets * minsize; i < this.graph.N; i++)
			{
				labels[i] = i % this.countOfSubsets;
			}

			int[] InterEdges = new int[this.countOfSubsets];
			int sumOfAllInterSubsetEdges = 0;
			// Für jeden Knoten
			for (int i = 0; i < this.graph.N; i++)
			{
				// Für jede Kantenmenge der Adjazenzliste
				foreach(List<Kante> es in this.graph.E[i].Values)
				{
					// Für jede Kante der Kantenmenge (besteht evtl. aus parellen)
					foreach(Kante e in es)
					{
                        if (labels[i] != labels[e.Nach])
                        {
                            InterEdges[i % this.countOfSubsets]++;
                            sumOfAllInterSubsetEdges++;
                        }
                    }
				}
			}
			
			sumOfAllInterSubsetEdges /= 2;
			
			Partition res = new Partition (labels, InterEdges, this.countOfSubsets, sumOfAllInterSubsetEdges);
			
			return res;
		}
		
		public Partition getStartHeuristic3 ()
		{
			int[] labels = new int[this.graph.N];
			int[] subsetSize = new int[this.countOfSubsets];
			
			int minsize = this.graph.N / this.countOfSubsets;
			
			BinaryHeap<DijkstraKnoten> pq = new BinaryHeap<DijkstraKnoten> ();
			
			// Init
			for (int i = 0; i < this.graph.N; i++)
			{
				labels[i] = -1;
				((DijkstraKnoten)this.graph.V[i]).distance = -1 * this.graph.E[i].Count;
				pq.insert ((DijkstraKnoten)this.graph.V[i]);
			}
			
			
			// Labeling
			int currentLabel = 0;
			
			while (currentLabel < this.countOfSubsets && !pq.isEmpty())
			{
				int id = pq.getMinId ();
				labels[id] = currentLabel;
				int oldsize = subsetSize[currentLabel];
				subsetSize[currentLabel]++;
				
				if(subsetSize[currentLabel] == minsize)
				{
					DijkstraKnoten head2 = pq.extractHead ();
					head2.distance += Math.Abs (subsetSize[currentLabel] - oldsize);
					if (head2.distance < 0)
						pq.insert (head2);
					currentLabel++;
					
					continue;
				}
				
				foreach (List<Kante> es in this.graph.E[id].Values)
				{
					foreach (Kante e in es)
					{
						int nach = e.Nach;
						if(labels[nach] == -1)
						{
							labels[nach] = currentLabel;
							DijkstraKnoten temp = (DijkstraKnoten)this.graph.V[nach];
							pq.decreaseKey (temp.getHeapPos (), temp.distance + 1);
							subsetSize[currentLabel]++;
						}
					}
					if (subsetSize[currentLabel] == minsize)
						break;
				}
				
				DijkstraKnoten head = pq.extractHead();
				
				head.distance += Math.Abs(subsetSize[currentLabel] - oldsize - 1);
				if(head.distance < 0)
					pq.insert(head);
				if (subsetSize[currentLabel] == minsize)
					currentLabel++;
			}
			
			// Nachlabeln
			
			SortedList<int, List<int>> max = new SortedList<int, List<int>> ();
			for (int i = 0; i < this.graph.N; i++)
			{
				if (labels[i] == -1)
				{
					foreach (List<Kante> es in this.graph.E[i].Values)
					{
						foreach (Kante e in es)
						{
							int val = labels[e.Nach];
							int index = -1;
							
							for(int a = 0 ;a < max.Count; a++)
							{
								if(max.Values[a].BinarySearch(val) >= 0)
								{
									index = a;
									break;
								}
							}
							
							if(index >= 0)
							{
								int key = max.Keys[index];
								key++;
								max.Values[index].Remove(val);
								
								if (max.ContainsKey (key))
								{
									int x = max.IndexOfKey (key);
									max.Values[x].Add (val);
									max.Values[x].Sort();
								} 
								else 
								{
									List<int> temp = new List<int> ();
									temp.Add (val);
									max.Add (key, temp);
								}
							}
							else if (max.ContainsKey(1) && val > 0)
							{
								int x = max.IndexOfKey (1);
								max.Values[x].Add(val);
								max.Values[x].Sort();
							}
							else if (val > 0)
							{
								List<int> temp = new List<int>();
								temp.Add(val);
								max.Add(1, temp);
							}
							//muss man nur einmal machen
							break;
						}
					}
					int j = max.Count-1;
					int k = -1;
					while(j >= 0)
					{
						for(int a = 0; a < max.Values[j].Count; a++)
						{
							//Console.WriteLine(max.Values[j][a]);
							if(subsetSize[max.Values[j][a]] <= minsize)
							{
								k = a;
								break;
							}
						}
						if(k >= 0)
							break;
						j--;
					}
					if(j >= 0)
					{
						labels[i] = max.Values[j][k];
						subsetSize[labels[i]]++;
					}
					else
					{
						j = this.countOfSubsets-1;
						while(j > 0 && subsetSize[j] > minsize)
						{
							j--;
						}
						labels[i] = j;
						subsetSize[j]++;
					}
				}
			}
			
			int[] InterEdges = new int[this.countOfSubsets];
			int sumOfAllInterSubsetEdges = 0;
			for (int i = 0; i < this.graph.N; i++)
			{
				// Für jede Kantenmenge der Adjazenzliste
				foreach (List<Kante> es in this.graph.E[i].Values)
				{
					// Für jede Kante der Kantenmenge (besteht evtl. aus parellen)
					foreach (Kante e in es)
					{
						if (labels[i] != labels[e.Nach])
						{
							InterEdges[i % this.countOfSubsets]++;
							sumOfAllInterSubsetEdges++;
						}
					}
				}
			}
			
			sumOfAllInterSubsetEdges /= 2;
			
			Partition res = new Partition (labels, InterEdges, this.countOfSubsets, sumOfAllInterSubsetEdges);
			
			return res;
		}
	}
}

